package q234_isPalindrome;

import CommonClass.Common.ListNode;

public class Solution {

    /**
     * 使用快慢指针的方法 将链表分为两部分 使空间复杂度降到O(1)
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;

        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 此时slow指针到达了链表的中间
        // 如果长度是偶数 则刚好是一半的位置 如果是奇数 则是中间对称的位置
        // 现在只需要将另外一段反转

        // 首先记录下slow的后一个节点 并且之后要将slow断开
        ListNode halfOfList = slow.next;
        slow.next = null;

        // 反转的流程
        while (halfOfList != null) {
            ListNode temp = halfOfList.next;
            halfOfList.next = slow;
            slow = halfOfList;
            halfOfList = temp;
        }

        // 反转完毕后 slow到达了另一端链表的尾部 然后我们再从头部开始与尾部slow一一比较值
        while(head != null){
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }

        return true;
    }
}
